package test.h0814;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        int[] nums={3,3,0,3};
        System.out.println(permuteUnique(nums));
    }

    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp=new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        //必须对数组排序，要不然后面去重的条件会失效
        Arrays.sort(nums);
        dfs(nums, temp,res, used);
        return res;
    }

    private static void dfs(int[] nums,List<Integer> temp, List<List<Integer>> res, boolean[] used) {
        if (temp.size() == nums.length) {
            res.add(new ArrayList<>(temp)); //添加temp的深拷贝
            return;
        }
        for ( int j = 0; j < nums.length; j++) {
            if (used[j]) continue;
            //确保只有前一个相同元素未被使用时，才会使用当前元素。
            if (j > 0 && nums[j] == nums[j - 1] && !used[j-1]) continue;
            used[j] = true;
            temp.add(nums[j]);
            dfs(nums,temp, res, used);
            temp.remove(temp.size() - 1);
            used[j] = false;
        }
    }
}
